package com.zb.kc.cms.test;


import org.junit.Test;

public class PlayGame {
    @Test
    public void name() {
        int[] num = {2, 2, 1, 3};
        int[] cnt = new int[num.length];

        System.out.print("排序前：");
        for (int i = 0; i < num.length; i++) {
            System.out.print(num[i] + "  ");
        }
        System.out.println();

        for (int i = 0; i < num.length; i++) {
            cnt[num[i]]++;
        }

        for (int i = 0; i < cnt.length; i++) {
            System.out.print(i + ": " + cnt[i] + "    ");
        }
        System.out.println();
        getPrefixSum(0, cnt);
        for (int i = 0; i < cnt.length; i++) {
            System.out.print(i + ": " + cnt[i] + "   ");
        }
        System.out.println();
        // 将计算好的前缀和数组，按value-1 从原始数组的末尾开始找到相应位置填充到原始数组的正确位置上
        // 浅拷贝原始数组给tmp
        int[] tmp = num.clone();
        // 从后往前遍历原始数组
        for (int i = tmp.length - 1; i >= 0; i--) {
            // 原始数组中从末尾开是第i个值
            int value = tmp[i];
            // 查询这个值应该在数组的哪一个位置
            int realIndex = cnt[value] - 1;
            // 将该值放入原始数组中正确的位置上
            num[realIndex] = tmp[i];
            // 该值所在的末尾位置往前位移一个
            cnt[value]--;
        }
        System.out.print("排序后: ");
        for (int i = 0; i < num.length; i++) {
            System.out.print(num[i] + "  ");
        }
    }

    // 递归方法计算前缀和
    public void getPrefixSum(int index, int[] cnt) {
        if (index >= cnt.length) {
            return;
        }
        int sum;
        if (index < 1) {
            sum = cnt[index];
        } else {
            sum = cnt[index] + cnt[index - 1];
        }
        cnt[index] = sum;
        index = index + 1;
        getPrefixSum(index, cnt);
    }

}
